Numerical solutions obtained by the Meshless Local Petrov-Galerkin (MLPG) method are presented for two dimensional steady-state heat conduction problems. The MLPG method is a truly mesh less approach, and neither the nodal connectivity nor the background mesh is required for solving the initial-boundary-value problem. The penalty method is adopted to efficiently enforce the essential boundary conditions, the moving least squares approximation is used for interpolation schemes and the Heaviside step function is chosen for test function. As the accuracy and runtime will depend on definition radiuses of the moving least squares approximation and the Heaviside step function; therefore, a genetic algorithm is carried out to determine the optimal values for these radiuses. The results show that the present method is very promising in solving engineering two dimensional steady-state heat conduction problems.